package com.origin.niuke.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * NC125 和为K的连续子数组
 * 算法：哈希 + 前缀和
 *
 * @author yezh
 * @data 2022/11/12 22:06
 */
public class NC125 {

    public int maxlenEqualK (int[] arr, int k) {
        // write code here
        int n = arr.length, ans = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>(n);
        map.put(0, 0);
        for (int i = 1; i <= n; i++) {
            // i 表示前 i 个元素的和
            sum += arr[i - 1];
            int target = sum - k;
            if (map.containsKey(target)) ans = Math.max(ans, i - map.get(target));
            map.putIfAbsent(sum, i);
        }
        return ans;
    }

}
